package Algorithm.Search;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * 快速排序算法
 * @author chenjunjie
 * @since 2018-04-17
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] a = new int[]{2, 17, 40, 5, 10, 51, 9, 23, 58, 36};
        System.out.println("排序后的结果：");
        sort(a,0,a.length-1);
        System.out.print(Arrays.toString(a));

    }

    /**
     * 快速排序逻辑
     * @param arr 原始数组
     * @param start 起始位置
     * @param end 结束位置（首次选取为基准数的位置）
     */
    public static void sort(int[] arr, int start, int end){
        if(start > end){
            //如果只有一个元素，就不用再排下去了
            return;
        }else {
            //如果不止一个元素，继续划分两边递归排序下去
            int partition = divide(arr, start, end);
            //已切割点为界（不包含切割点），将数据划分为两个小模块进行排序
            sort(arr, start, partition-1);
            sort(arr,partition+1, end);

        }


    }

    /**
     * 每个模块数据顺序调整逻辑
     * 左边交换，右边交换，不断循环
     * @param arr
     * @param start
     * @param end
     * @return 返回切割点位置
     */
    private static int divide(int[] arr, int start, int end) {
        //每次最开始都以最右边的元素作为基准值，
        //从左边开始与这个基准是比较，如果左边的数字比这个值大，就交换，
        //交换之后，然后在从右边往左边走（比较），比较到比基准值小就
        //
        int base = arr[end];
        while (start < end) {
            while (start < end && arr[start] <= base) {
                start++;
            }
            if (start < end) {
                //交换
                int temp = arr[start];
                arr[start] = arr[end];
                arr[end] = temp;
            }
            //从右边开始遍历，如果比基准值大，就继续向左走
            while (start < end && arr[end] >= base) {
                end--;
            }
            if (start < end) {
                //交换
                int temp = arr[start];
                arr[start] = arr[end];
                arr[end] = temp;
                //交换后，此时的那个被调换的值也同时调到了正确的位置(基准值左边)，因此左边也要同时向后移动一位
                start++;
            }
        }
        return end;
    }
}
